Branch and Bound

释义 Definition

“分支定界法；分枝界限法”：一种用于求解组合优化与整数规划问题的搜索框架。它把问题分解成若干子问题（branch 分支），并用上下界估计（bound 定界）来剪去不可能得到更优解的分支，从而减少搜索量并找到最优解。（也常用于旅行商问题 TSP、0-1 背包、调度等。）

发音 Pronunciation

/bræntʃ ænd baʊnd/

例句 Examples

We used branch and bound to find the optimal route.
我们用分支定界法来找到最优路线。

For large integer programs, branch and bound prunes many subproblems by comparing upper and lower bounds, which can dramatically reduce computation time.
对于大型整数规划，分支定界法通过比较上下界剪枝许多子问题，从而显著减少计算时间。

词源 Etymology

该术语由两个常见英语词组组合而成：branch（“分枝/分支”，指把原问题拆成一棵搜索树的子问题）与 bound（“界/界限”，指数学上的上界或下界）。它直观描述了方法的核心步骤：先“分支”，再用“界”来判断哪些分支不必继续搜索。

相关词 Related Words

• Backtracking
• Pruning
• Search Tree
• Integer Programming
• Mixed-Integer Programming
• Cutting Plane
• Lower Bound
• Upper Bound
• Combinatorial Optimization
• Dynamic Programming

文学与著作中的用例 Literary Works

• Introduction to Operations Research（Hillier & Lieberman）——在整数规划与组合优化章节中系统介绍分支定界法。
• Integer and Combinatorial Optimization（Nemhauser & Wolsey）——以更理论化方式讨论分支定界及其与割平面的关系。
• The Traveling Salesman Problem（Lawler 等编）——在经典 TSP 研究中频繁出现分支定界及其变体。
• Combinatorial Optimization: Algorithms and Complexity（Papadimitriou & Steiglitz）——作为经典算法框架之一被讨论与对比。